package pers.qianyu.month_202012.date_20201204;

import java.util.*;

/**
 * [Leetcode 每日一题]
 * 659. 分割数组为连续子序列
 * https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/
 *
 * @author mizzle rain
 * @date 2020年12月4日14:42:58
 */
public class IsPossible2 {
    /**
     * 哈希表 + 小顶堆
     */
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<Integer>> dict = new HashMap<>();
        for (int num : nums) {
            if (!dict.containsKey(num)) {
                dict.put(num, new PriorityQueue<>());
            }
            if (dict.containsKey(num - 1)) {
                PriorityQueue<Integer> q = dict.get(num - 1);
                int pre = q.poll();
                if (q.isEmpty()) {
                    dict.remove(num - 1);
                }
                dict.get(num).add(pre + 1);
            } else {
                dict.get(num).offer(1);
            }
        }
        for (PriorityQueue<Integer> q : dict.values()) {
            if (q.peek() < 3) {
                return false;
            }
        }
        return true;
    }
}
